package leetcode;

public class ValidParentheses20 {
    class ArrayStack {
        Object[] array;
        int top = 0;

        public ArrayStack(int capacity) {
            array = new Object[capacity];
        }

        public boolean push(Object val) {
            if (isFull()) {
                return false;
            }
            array[top++] = val;
            return true;
        }

        public Object pop() {
            if (isEmpty()) {
                return null;
            }
            return array[--top];
        }

        public Object peek() {
            if (isEmpty()) {
                return null;
            }
            return array[top - 1];
        }

        public boolean isEmpty() {
            return top == 0;
        }

        public boolean isFull() {
            return top == array.length;
        }
    }

    class LinkedListStack {
        class Node {
            Object val;
            Node next;

            public Node(Object val, Node next) {
                this.val = val;
                this.next = next;
            }
        }

        Node head = new Node(null, null);
        int size = 0;
        int capacity;

        public LinkedListStack(int capacity) {
            this.capacity = capacity;
        }

        public boolean isFull() {
            return size == capacity;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean push(Object val) {
            if (isFull()) {
                return false;
            }
            head.next = new Node(val, head.next);
            size++;
            return true;
        }

        public Object pop() {
            if (isEmpty()) {
                return null;
            }
            Node first = head.next;
            head.next = first.next;
            size--;
            return first.val;
        }

        public Object peek() {
            if (isEmpty()) {
                return null;
            }
            return head.next.val;
        }
    }

    boolean isValid(String s) {
        ArrayStack stack = new ArrayStack(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{') {
                stack.push('}');
            }else if (c =='['){
                stack.push(']');
            }else if(c == '('){
                stack.push(')');
            }
            else{
                if(!stack.isEmpty() && c == (char)stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
